package com.example.robertluozizhao.java.arithmetic;

/**
 * Created by Lzz on 5/31/2020.
 * 排序算法
 * 1.快速排序
 * 2.选中排序（记录Max Min索引）
 */

public class rankArith {


    public static void main(String[] args) {

        int[] testArray = {8, 3, 4, 7, 10, 9, 5, 6, 1, 7, 8, 5, 47, 2};

//        //1.快速排序
//        quickSort(testArray,0,testArray.length-1);
//        //2.选择排序
//        selectSort(testArray);

        //3.插入排序
//        insertionSort(testArray);
        insertSort(testArray);


        for (int i : testArray) {
            System.out.print(i + ",");
        }
    }

    private static void quickSort(int[] testArray, int startIndex, int length) {
        /**
         * 1.标记开始元素  -> 最终置换的元素
         * 2.左启找到比标记元素大（在后） 且 右启找到比标记元素小（在先） -> 置换
         * 3.左与右相遇点 -> 与标记元素置换
         * 4.相遇点划分两数组 -> 重复步骤
         *
         * 注意：基准点在左，要先从右起查找
         */

        if (startIndex > length) {
            return;
        }

        int startElemem = testArray[startIndex];
        int leftIndex = startIndex;
        int rightIndex = length;
        int temp;

        while (leftIndex < rightIndex) {


            /**
             * 注意：基准点在左，要先从右起查找
             */
            while (testArray[rightIndex] >= startElemem && leftIndex < rightIndex) {
                rightIndex--;
            }

            while (testArray[leftIndex] <= startElemem && leftIndex < rightIndex) {
                leftIndex++;
            }


            if (leftIndex < rightIndex) {
                temp = testArray[leftIndex];
                testArray[leftIndex] = testArray[rightIndex];
                testArray[rightIndex] = temp;
            }
        }

        testArray[startIndex] = testArray[leftIndex];
        testArray[leftIndex] = startElemem;

        quickSort(testArray, leftIndex + 1, length);
        quickSort(testArray, startIndex, leftIndex - 1);

    }


    private static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] > array[maxIndex]) {
                    maxIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[maxIndex];
            array[maxIndex] = temp;
        }
    }

    private static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            //当前元素i
            int current = array[i];
            //比较元素j
            int j = i - 1;
            while (j >= 0 && j < array.length - 1) {
                if (current > array[j]) {//当前 > 比较 （比较元素后移一位）
                    array[j + 1] = array[j];
                    if (j==0){
                        array[j] = current;
                    }
                } else {
                    array[j + 1] = current;
                    break;
                }
                j--;
                printTest(array);
            }
        }
    }

   public static void insertionSort(int[] arr) {
       int len = arr.length;
       int preIndex, current;
        for(int i = 1; i < len; i++) {
            preIndex = i - 1;
            current = arr[i];
            while(preIndex >= 0 && arr[preIndex] < current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
                printTest(arr);
            }
            arr[preIndex + 1] = current;

            System.out.println("*************************************************************");
            printTest(arr);
        }
    }

    private static void printTest(int[] testArray){
        for (int i : testArray) {
            System.out.print(i + ",");
        }
        System.out.println();
    }
}
